package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 1139. 最大的以 1 为边界的正方形
 *
 * @author liw
 * @version 1.0
 * @date 2021/9/3 17:19
 */
public class Largest1BorderedSquare {

    public static void main(String[] args) {
        Largest1BorderedSquare test = new Largest1BorderedSquare();
        // 9
        int[][] arr = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};

        // 1
//        int[][] arr = {{1,1,0,0}};
        int i = test.largest1BorderedSquare(arr);
        System.out.println(i);
    }

    public int largest1BorderedSquare(int[][] grid) {
        int a = grid.length;
        int b = grid[0].length;
        int max = 0;
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                if (grid[i][j] == 1) {
                    int m = j > 0 ? grid[i][j - 1] : 0;
                    int n = i > 0 ? grid[i - 1][j] : 0;
                    int x = (m >> 8) + 1;
                    int y = (n & 0XFF) + 1;
                    grid[i][j] = (x << 8) + y;
                    int min = Math.min(x, y);
                    for (int k = 0; k < min; k++) {
                        int item = grid[i][j - k];
                        int it = item & 0XFF;
                        if (it < k + 1) {
                            continue;
                        }
                        item = grid[i - k][j];
                        it = item >> 8;
                        if (it < k + 1) {
                            continue;
                        }
                        max = Math.max(max, k + 1);
                    }
                }
            }
        }
        return max * max;
    }


}
